package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         678,
		Discription: "带*的括号匹配",
		Level:       2,
		Labels: map[string]int{
			"栈":  1,
			"双栈": 1,
		},
	})
}

func CheckValidString(s string) bool {
	//将下标进栈，因为后边要根据下标判断是否能和*匹配，每种栈只会进一个值所以不影响
	s1 := make([]int, 0)
	s2 := make([]int, 0)
	for i := 0; i < len(s); i++ {
		ch := s[i]
		if ch == '*' {
			s2 = append(s2, i)
			continue
		}

		if ch == '(' {
			s1 = append(s1, i)
			continue
		}

		//优先和括号栈匹配
		if len(s1) > 0 {
			s1 = s1[:len(s1)-1]
		} else {
			//括号栈没了找*栈
			if len(s2) == 0 {
				return false
			}

			s2 = s2[:len(s2)-1]
		}
	}

	//遍历结束后两个栈可能都不会空，尝试让*栈去抵消括号栈
	for len(s1) != 0 && len(s2) != 0 {
		//每个*的元素大于(就行
		if s1[len(s1)-1] < s2[len(s2)-1] {
			s1 = s1[:len(s1)-1]
			s2 = s2[:len(s2)-1]
		} else {
			return false
		}
	}

	//最后看括号栈是否还有残留
	return len(s1) == 0
}
